const partition = (arr, startIndex, endIndex)=>{
  // 取第一个位置的元素作为基准元素（也可以选择随机位置）
  let pivot = arr[startIndex];
  let mark = startIndex;

  for(let i=startIndex+1; i<=endIndex; i++){
    if(arr[i]<pivot){
      mark ++;
      let p = arr[mark];
      arr[mark] = arr[i];
      arr[i] = p;
    }
  }

  arr[startIndex] = arr[mark];
  arr[mark] = pivot;
  return mark;
}
const quickSort = (arr, startIndex, endIndex)=>{
  // 递归结束条件：startIndex大等于endIndex的时候
  if (startIndex >= endIndex) {
    return;
  }
  // 得到基准元素位置
  let pivotIndex = partition(arr, startIndex, endIndex);
  // 根据基准元素，分成两部分递归排序
  quickSort(arr, startIndex, pivotIndex - 1);
  quickSort(arr, pivotIndex + 1, endIndex);
}
const run = ()=>{
  const arr = [4,4,6,5,3,2,8,1];
  quickSort(arr, 0, arr.length-1);
  console.log(arr)
}
run();